(* Exercise 1.1a *)

(* -- supplied code -- *)
type key = string;

datatype tree = LEAF | TREE of tree * key * tree;

val empty = LEAF;

fun insert (k', LEAF) = TREE (empty, k', empty)
  | insert (k', TREE (l, k, r)) = if (k' < k)
				  then TREE (insert (k', l), k, r)
				  else if (k' > k)
				       then TREE (l, k, insert (k', r))
				       else TREE (l, k, r);    (* k' = k *)
(* -- end of supplied code -- *)


(* member -- look up a key in the binary search tree *)
(* illustrate andalso and orelse boolean operations *)
val rec member : (key * tree) -> bool =
 fn (k', LEAF) => false
  | (k', TREE (l, k, r)) => ((k'<k) andalso member (k', l))
			    orelse (k'=k)
			    orelse ((k'>k) andalso member (k', r));

(* testing *)
val op ++ = insert;
infix ++;

val t1 = empty;
val t2 = "A" ++ t1;
val t3 = "B" ++ t2;
val t4 = "C" ++ t3;
val t5 = "A" ++ t4;

use "assert.sml"; (* load our testing package *)

assert (not (member ("A", t1)), "A1");
assert (member ("A", t2), "A2");
assert (member ("A", t3), "A3");
assert (member ("A", t4), "A4");
assert (member ("A", t5), "A5");

assert (not (member ("B", t1)), "B1");
assert (not (member ("B", t2)), "B2");
assert (member ("B", t3), "B3");
assert (member ("B", t4), "B4");
assert (member ("B", t5), "B5");

assert (not (member ("C", t1)), "C1");
assert (not (member ("C", t2)), "C2");
assert (not (member ("C", t3)), "C3");
assert (member ("C", t4), "C4");
assert (member ("C", t5), "C5");

(* illustrate system primitives *)
OS.Process.exit OS.Process.success;
